﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


 public class Node {
    public int val;

    public Node next;
    public Node random;
    public Node(int val=0,Node next=null,Node random=null) {

        this.val = val;
        this.next = next;
        this.random = random;

    
    }


}
class Sol138
{
    public Node CopyRandomList(Node head)//这个方法在链表里面有重复值的时候，key会重复，然后失效
    {

        if (head == null)
        {
            return head;
        }
        Dictionary<Node, Node> map = new Dictionary<Node, Node>();
        Node newHead=new Node(head.val) ;
        Node newHeadCur = newHead;
        Node headCur= head;
        map.Add(headCur, newHeadCur);
        while (headCur.next != null)
        {
            //Console.WriteLine(head.val);
           
            newHeadCur.next = new Node(headCur.next.val);
            map.Add(headCur.next, newHeadCur.next);

            headCur = headCur.next;
            newHeadCur = newHeadCur.next;
        }
         newHeadCur = newHead;
         headCur = head;

        while (headCur!= null)
        {
           
            if (headCur.random!=null)
            {
                //Console.WriteLine("random:  "+headCur.random.val);
                newHeadCur.random = map[headCur.random]; //使用head的值，去查找对应的node
            }

           


            headCur = headCur.next;
            newHeadCur = newHeadCur.next;
        }






        return newHead;
    }
    //下面这个方法的区别就是，一个key是headCur.random.val，一个是headCur.random
    Dictionary<Node, Node> map = new Dictionary<Node, Node>();//这个表的作用是记录node是否被创建newnode了
        public Node CopyRandomList2(Node head)//哈希加回溯
        {

            if (head == null)
            {
                return head;
            }
        
       
        
        
            if(!map.ContainsKey(head))//没有创建过的才创建
            {
                Console.WriteLine(head.val);
                Node newHead = new Node(head.val);
                map.Add(head, newHead);

                newHead.next = CopyRandomList(head.next);//这个递归创建了很多next
                newHead.random = CopyRandomList(head.random);//这个节点创建好的时候就指向，否则就等创建后再指向，相当于从后向前random
            //没有创建好先跳过

            }
            return map[head];
        }

}

class Program138
{
    static void Main138()
    {

        Node head=new Node(7);
        Node second=new Node(13);
        Node third=new Node(11);
        Node fourth=new Node(10);
        Node fif=new Node(1);
        head.next= second; 
        second.next= third;
        second.random = head;
        third.random = fif;
        third.next = fourth;
        fourth.next = fif;
        fourth.random = third;
        fif.random = head;

        //while (head != null)
        //{
        //    Console.WriteLine(head.val);
        //    head = head.next;
        //}


        Sol138 sol138 = new Sol138();
        Node res = sol138.CopyRandomList(head);
        Console.WriteLine("head指向"+res.val);
        while (res != null)
        {
            Console.WriteLine(res.val);
            if (res.random != null)
            {
                Console.WriteLine("random:  " + res.random.val);
            }
               
            res = res.next;
        }




    }

}